/*
 * 1140. 快速幂
 * 计算an % b，其中a，b和n都是32位的整数。
 * https://www.lintcode.com/problem/fast-power/description
 * 
 * 样例
 * 例如 231 % 3 = 2
 * 例如 1001000 % 1000 = 0
 * 
 * 挑战
 * O(logn)
 * 
 * 2018.06.13 @jeyming
 */
package fast_power_1140;

public class Fast_power_1140 {
	/**
	 * @param a: A 32bit integer
	 * @param b: A 32bit integer
	 * @param n: A 32bit integer
	 * @return: An integer
	 */
	public static int fastPower(int a, int b, int n) {
		// write your code here
//		if((n == 0) || (a == 1)) {
//			if(b == 1)
//				return 0;
//			return 1;
//		}else if(a > b) {
//			return (a - b) * n % b;
//		} else if(a == b) {
//			return 0;
//		} else {
//			int cnt = 1;
//			long tmpA = a; //a^x
//			while((tmpA <= b) && (cnt < n)) {
//				tmpA *= a;
//				++cnt;
//			}
//			if(tmpA < b) {
//				return (int) tmpA;
//			}else if(n % cnt == 0) {
//				return (int) ((Math.pow((tmpA - b), (n / cnt))) % b);
//			} else {
//				return (int) ((Math.pow((tmpA - b), (n / cnt)) * Math.pow(a, (n % cnt))) % b);
//			}
//		}
		if(n == 0)
			return 1 % b;
		if(n == 1)
			return a % b;
		long tmp = fastPower(a, b, n /2);
		if((n & 1) == 1)
			return (int) (((tmp * tmp) % b) * a % b) ;
		else
			return (int) (tmp * tmp % b);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		System.out.println(fastPower(2,3,31));
//		System.out.println(fastPower(100,1000,1000));
//		System.out.println(fastPower(3,7,5));
//		System.out.println(fastPower(2,10,1));
//		System.out.println(fastPower(2,2147483647,2147483647));
		System.out.println(fastPower(101,10000007,1000001));
	}

}
